#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

void insertion_sort_old(int array[], int size)
{
    int j;      //未排序的第一个的索引位置，初始值=1
    for (j = 1; j < size; j++)
    {
        int key = array[j];
        int n = j-1;
        while (n >= 0 && array[n] < key)
        {
            array[n+1] = array[n];
            n--;
        }
        array[n+1] = key;
    }
}

void insertion_sort(vector<int> &array)
{
    int i;      //排好序的最后一个的索引位置，初始值=0
    int j;      //未排序的第一个的索引位置，初始值=1
    for (i = 0, j = 1; j < array.size(); i++, j++)
    {
        int n = j;
        while (n > 0 && array[n-1] < array[n])
        {
            swap(array[n-1], array[n]);
            n--;
        }
    }
}

int main(int argc, char const *argv[])
{
    vector<int> a{5, 2, 4, 1, 3};

    insertion_sort(a);
    
    for (auto n : a){
        cout<<n<<" ";
    }
    
    cout<<endl;

    int a1[] = {5, 2, 4, 1, 3};

    insertion_sort_old(a1, sizeof(a1)/sizeof(int));
    
    for (auto n : a1){
        cout<<n<<" ";
    }
    
    cout<<endl;

    return 0;
}
